package com.love.labuladong.twopoint.slidewindow;

import java.util.Arrays;

/**
 * @Author : zh
 * @Description : 3.无重复字符的最长字串
 * @Date : 2024-08-30 15:35
 */
public class NoDiffMaxSub {



    public static int lengthOfLongestSubString(String str){
        char[] s = str.toCharArray();
        int n = s.length;
        // char -> int -> 0 ~ 255
        // 每一种字符上次出现的位置
        int[] last = new int[256];
        // 所有字符都没有上次出现的位置
        Arrays.fill(last,-1);
        int ans = 0;
        for (int l = 0, r = 0; r < n; r++){
            // 关键
            l = Math.max(l,last[s[r]] + 1);
            ans = Math.max(ans, r - l + 1);
            last[s[r]] = r;
        }
        return ans;
    }


    // 思路：
    // 1.左指针用来标记[不重复字符串的开始位置]，右指针用来遍历所有字符的。
    // 2.last[]记录各个字母上一次出现的位置，指针不回退，所以某些字符出现多次，那该字符的上一次位置可能是会改变的，所以遍历一个，更新一次
    // 发现一个问题，它每一次 l 都会去比较，该字母的上一次位置 + 1，而不是先比较 s[r] 是否出现过，然后再更新 l 的位置
    // 思考了一下，每次做判断，和 直接比较交换，是等同的问题。时间复杂度也一样，上述只是向上更跳跃了一步

    public static int lengthOfLongestSubString2(String str){
        char[] s = str.toCharArray();
        int n = s.length;
        // char -> int -> 0 ~ 255
        // 每一种字符上次出现的位置
        int[] last = new int[256];
        // 所有字符都没有上次出现的位置
        Arrays.fill(last,-1);
        int ans = 0;
        for (int l = 0, r = 0; r < n; r++){
            if(last[s[r]] != -1){
                l = Math.max(l,last[s[r]] + 1);
            }
            ans = Math.max(ans, r - l + 1);
            last[s[r]] = r;
        }
        return ans;
    }



    public static void main(String[] args) {
        String s = "cacbcaefgh";
        System.out.println(lengthOfLongestSubString2(s));
    }


}
